package leetcode_81_100;

import org.apache.commons.lang3.SerializationUtils;
import utils.TreeNode;

import org.apache.commons.beanutils.BeanUtils;

import java.lang.reflect.InvocationTargetException;
import java.util.ArrayList;
import java.util.List;

public class generateTrees_95 {
    /**
     * 生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。
     * 可以按 任意顺序 返回答案。
     * @param n
     * @return
     */
    public List<TreeNode> generateTrees(int n) throws InvocationTargetException, IllegalAccessException {
        /**
         * 要求中序，前序，后序都要含有
         * 递归写法，写不出来
         */
        List<TreeNode> res = new ArrayList<>();
        TreeNode node=new TreeNode();
        dfsMiddle(n,n,node,node,res);
        return res;
    }

    /**
     * 中序递归构造二叉树失败
     * 当时以为是普通的二叉树，没有注意带二叉搜索树的性质
     * @param num 当前节点的数字
     * @param n 需要的节点数量
     * @param node 当前的二叉树头节点
     * @param end  始终指向当前的二叉树最后一个节点
     * @param res
     */
    public void dfsMiddle(int num,int n,TreeNode node,TreeNode end,List<TreeNode> res) throws InvocationTargetException, IllegalAccessException {
        end.val=num;    //给最后一个节点赋值
        // 进入左节点
        if (num == 1) { //完成一个二叉树就返回
            //复制当前树并且加到结果中
            TreeNode newNode= (TreeNode) SerializationUtils.clone(node);
            res.add(newNode);
            return;
        }
        end.left=new TreeNode();
        dfsMiddle(num-1,n,node,end.left,res);
        end.left=null;
        // 进入右节点
        end.right=new TreeNode();
        dfsMiddle(num-1,n,node,end.right,res);
        end.right=null;
    }


    /**
     * 看正解
     * 利用二叉搜索树性质，进行递归
     * 二叉搜索树的性质。左子树的所有值小于根节点，右子树的所有值大于根节点。
     * 把每个数字作为根节点，然后把所有可能的左子树和右子树组合
     * @param n
     * @return
     */
    public List<TreeNode> generateTrees2(int n) {
        List<TreeNode> ans = new ArrayList<TreeNode>();
        if (n == 0) {
            return ans;
        }
        return getAns(1, n);

    }

    private List<TreeNode> getAns(int start, int end) {
        List<TreeNode> ans = new ArrayList<TreeNode>();
        //此时没有数字，将 null 加入结果中
        if (start > end) {
            ans.add(null);
            return ans;
        }
        //只有一个数字，当前数字作为一棵树加入结果中
        if (start == end) {
            TreeNode tree = new TreeNode(start);
            ans.add(tree);
            return ans;
        }
        //尝试每个数字作为根节点
        for (int i = start; i <= end; i++) {
            //得到（start ~ i - 1）这些数字组成所有可能的左子树
            List<TreeNode> leftTrees = getAns(start, i - 1);
            //得到（i + 1 ~ end）这些数字组成所有可能的右子树
            List<TreeNode> rightTrees = getAns(i + 1, end);
            //左子树右子树两两组合，此时位于树
            for (TreeNode leftTree : leftTrees) {
                for (TreeNode rightTree : rightTrees) {
                    TreeNode root = new TreeNode(i); //该层递归的根节点
                    root.left = leftTree;
                    root.right = rightTree;
                    //加入到最终结果中
                    ans.add(root);
                }
            }
        }
        return ans; //每一层递归运行完，都会得到一组由下一层递归的结果集组合而成的结果集
    }
}
